package sort

func Bubblesort(array []int) {
	length := len(array)
	for i := 0; i < length; i++ {
		for j := 0; j < length-1-i; j++ {
			if array[j] > array[j+1] {
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
}

func Insertsort(array []int) {
	length := len(array)
	for i := 0; i < length-1; i++ {
		p := array[i+1]
		pos := 0
		// 查找指定的插入位置
		for pos <= i && array[pos] < p {
			pos++
		}
		// 移动pos后面的元素
		for k := i + 1; k > pos; k-- {
			array[k] = array[k-1]
		}
		// 插入指定位置的值
		array[pos] = p
	}
}

func Insertsort2(array []int) {
	length := len(array)
	for i := 1; i < length; i++ {
		p := array[i]
		pos := i
		for ; pos > 0 && array[pos-1] > p; pos-- {
			array[pos] = array[pos-1]
		}
		// 插入指定位置的值
		array[pos] = p
	}
}

func Selectsort(array []int) {
	length := len(array)
	for i := 0; i < length; i++ {
		pos := i
		for j := i + 1; j < length; j++ {
			if array[j] < array[pos] {
				// 记录最小值的下标
				pos = j
			}
		}
		// 交换数组下标值
		array[i], array[pos] = array[pos], array[i]
	}
}

func MergeSort(array []int) {
	length := len(array)
	result := make([]int, length)
	start := 0
	end := length - 1
	mergesort0(array, result, start, end)
}

// 递归调用
func mergesort0(array []int, result []int, low int, high int) {
	if low < high {
		mid := (low + high) >> 1
		mergesort0(array, result, low, mid)
		mergesort0(array, result, mid+1, high)
		merge(array, result, low, high)
	}
}

// 合并数组
func merge(array []int, result []int, low int, high int) {
	start := low
	left := low
	mid := (low + high) / 2
	right := mid + 1
	for left <= mid && right <= high {
		if array[left] < array[right] {
			result[start] = array[left]
			left++
		} else {
			result[start] = array[right]
			right++
		}
		start++
	}
	for left <= mid {
		result[start] = array[left]
		start++
		left++
	}

	for right <= high {
		result[start] = array[right]
		start++
		right++
	}

	for i := low; i <= high; i++ {
		array[i] = result[i]
	}
}

// 快速排序
func Quicksort(array []int) {
	low := 0
	high := len(array) - 1
	quicksort0(array, low, high)
}

func quicksort0(array []int, low int, high int) {
	if low >= high {
		return
	}
	// index := partition(array, low, high)
	index := partition2(array, low, high)
	quicksort0(array, low, index-1)
	quicksort0(array, index+1, high)
}

func partition(array []int, low int, high int) int {
	p := array[low]
	left := low
	right := high

	pos := low
	for left <= right {
		elem := array[left]
		if elem >= p {
			left++
		} else {
			for i := left; i > low; i-- {
				array[i] = array[i-1]
			}
			array[low] = elem
			pos++
		}
	}
	return pos
}

func partition2(array []int, low, high int) int {
	pivot := low
	pos := low + 1
	for i := pos; i <= high; i++ {
		if array[i] < array[pivot] {
			array[i], array[pos] = array[pos], array[i]
			pos += 1
		}
	}
	array[pivot], array[pos-1] = array[pos-1], array[pivot]
	return pos - 1
}

func BinarySearch(array []int, key int) int {
	low := 0
	high := len(array)
	mid := (low + high) >> 1
	for low < high {
		if array[mid] == key {
			return mid
		} else if array[mid] < key {
			low = mid
			mid = (low + high) >> 1
		} else if array[mid] > key {
			high = mid
			mid = (low + high) >> 1
		}
	}
	return -1
}
